The present invention relates to a method for correlating discrete-time signal segments, wherein a predetermined signal section in a signal is determined by means of the correlation, in particular for a signal transmission system, wherein the system having the known signal segment is sent from a transmitter to a receiver, and the position of the known signal segment in the signal is determined in the receiver by means of the correlation between the received signal and the known signal segment.
Although usable in any digital message transmission system, the present invention as well as its underlying problems will be explained in relation to UMTS (Universal Mobile Telephone Systems) systems.
To detect a known signal segment (also referred to hereinafter as “test signal”) in a received signal, the correlation of the test signal that is known and stored there with the received signal is usually carried out in the receiver.
This position determination of the test signal serves, for example, to determine the starting instant of the test signal within the received signal, i.e., for purposes of synchronization.
Of particular interest hereby are test signals that have good autocorrelation properties that are noted for a high autocorrelation coefficient in the relative time shift zero and, additionally, for low values for the autocorrelation to time shifts different from zero.
Moreover, these test signals should have a systematic structure that makes it possible to carry out the necessary correlations with the fewest arithmetic operations possible. A special class of discrete-time test signals in this sense form “hierarchical codes” or sequences.
A hierarchical sequence h(k) of the nth order is formed systematically out of n not necessarily different short sequencesh1=(h1(0),h1(1), . . . ,h1(m1−1)),h2=(h2(0),h2(1), . . . ,h2(m2−1)), . . . ,hn=(hn(0),hn(1), . . . ,hn(mn−1))having elements hi(k)ε{−1, +1}, according to the following construction scheme:x1(k)=h1(k),k=0, . . . ,m1−1,  (1)xi+1(k)=hi+1(k div mi+1)·xi(k mod mt),
                              k          =          0                ,                  .                                          .                                          .                ⁢                                  ,                              (                                          ∏                                  l                  =                  1                                                  i                  +                  1                                            ⁢                                                          ⁢                              m                1                                      )                    -          1                ,                  i          =          1                ,                  .                                          .                                          .                ⁢                                  ,                  n          -          1                                    (        2        )                                                      h            ⁡                          (              k              )                                =                                    x              n                        ⁡                          (              k              )                                      ,                  k          =          0                ,                  .                                          .                                          .                ⁢                                  ,                              (                                          ∏                                  l                  =                  1                                n                            ⁢                                                          ⁢                              m                1                                      )                    -          1.                                    (        3        )            
The expense to correlate such a hierarchical sequence with another signal or another sequence can be reduced considerably in known fashion by means of a rapid correlation in multiple steps, as compared to a direct realization. Moreover, hierarchical sequences can be found that have good correlation properties and are therefore well-suited in the sense mentioned initially as test signals for synchronization.
The mentioned procedure for the cost-efficient, rapid hierarchical correlation will be explained further hereinafter, because the method according to the invention described later is based on it. The received signal, with which the test signal is to be correlated in the receiver, is referred to as s(k). Without restricting the generality, it suffices to consider hierarchical sequences of the 2nd order (i.e., n=2), because hierarchical sequences having more than two hierarchical levels are always formed successively out of two subsequences, according to the above equations. The correlation should be carried out for each instant k.
The correlation result v(k) is thereby as follows:
                                                                        v                ⁡                                  (                  k                  )                                            =                                                ∑                                      j                    =                    0                                                        n                    -                    1                                                  ⁢                                                                  ⁢                                                      h                    ⁡                                          (                      j                      )                                                        ·                                      s                    ⁡                                          (                                              j                        +                        k                                            )                                                                                                                                              =                                                ∑                                      j                    =                    0                                                        n                    -                    1                                                  ⁢                                                                  ⁢                                                                            h                      2                                        ⁡                                          (                                              j                        ⁢                                                                                                  ⁢                        div                        ⁢                                                                                                  ⁢                                                  m                          2                                                                    )                                                        ·                                                            h                      1                                        ⁡                                          (                                              j                        ⁢                                                                                                  ⁢                        mod                        ⁢                                                                                                  ⁢                                                  m                          1                                                                    )                                                        ·                                      s                    ⁡                                          (                                              k                        +                        j                                            )                                                                                                                              (        4        )                                                                    =                                                ∑                                      i                    =                    0                                                                              n                      2                                        -                    1                                                  ⁢                                                                  ⁢                                                                            h                      2                                        ⁡                                          (                      i                      )                                                        ·                                                                                                              ∑                                                      j                            =                            0                                                                                                              n                              1                                                        -                            1                                                                          ⁢                                                                                                  ⁢                                                                                                            h                              1                                                        ⁡                                                          (                              j                              )                                                                                ·                                                      s                            ⁡                                                          (                                                              k                                +                                                                  i                                  ·                                                                      n                                    1                                                                                                  +                                j                                                            )                                                                                                                          ︸                                                                                                                v                          1                                                ⁡                                                  (                                                      k                            +                                                          i                              ·                                                              n                                1                                                                                                              )                                                                    :=                                                                                                                                              =                                                ∑                                      i                    =                    0                                                                              n                      2                                        -                    1                                                  ⁢                                                                  ⁢                                                                            h                      2                                        ⁡                                          (                      i                      )                                                        ·                                                            ∑                                              j                        =                        0                                                                                              n                          1                                                -                        1                                                              ⁢                                                                                  ⁢                                                                  v                        1                                            ⁡                                              (                                                  k                          +                                                      i                            ·                                                          n                              1                                                                                                      )                                                                                                                                                    (        5        )            
FIG. 2 illustrates the known hierarchical correlation procedure using the example of a hierarchical sequence of the 2nd order. The arithmetic steps are illustrated using lines.
The short subsequences are given by h1=(+1, +1, −1, +1) and h2=(+1, −1, +1, +1). The total sequence is therefore h=(+1, +1, −1, +1, −1, −1, +1, −1, +1, +1, −1, +1, +1, +1, −1, +1). In the first step or the first subcorrelation step TK1, the subcorrelation v1(k) is determined. In the second step or the second subcorrelation step TK2, the searched-for correlation v(k) is determined from this intermediate result. As time k continues, as indicated in FIG. 2 using the bold lines, three known results can be referred back to in each case, and only one new calculation need be carried out in the subcorrelation step TK1, namely for the most recent ones, by the sampling of received signal values of the signal s(k).
Further correlation steps result accordingly for n>2 subsequences according to the same basic principle.